package com.cn.algorithm02.class15;

import java.util.Arrays;
import java.util.Comparator;

/***
 * @author: hels
 * @description: 一个会议室有多个会议，如何可以安排尽可能多的会议，返回最大的会议数量
 * ①会议用数组表示，两个元素表示起止时间
 * ②会议时间不能有重叠
 * 使用贪心算法，或者说递归过程中尽量不要对全局变量进行赋值运算，否则极易产生问题
 **/
public class C01_BestRange {
    public static class Meeting {
        public int start;

        @Override
        public String toString() {
            return "Meeting{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }

        public int end;

        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void pt(Meeting[] arr) {
        for (Meeting m: arr ) {
            System.out.printf(m.toString() + "  ");
        }
    }
    public static void main(String[] args) {
        Meeting m0 = new Meeting(5, 13);
        Meeting m1 = new Meeting(11, 13);
        Meeting m2 = new Meeting(4, 19);
        Meeting m3 = new Meeting(0, 10);
        //Meeting m4 = new Meeting(5, 8);
        Meeting[] arr = randomGenerate(5,20);
//        Meeting[] arr = {/*m0,*/ m1/*,m2*/, m3};
        pt(arr);
        System.out.println();
        System.out.println(bestRange2(arr));
        System.out.println(bestRange3(arr));
        System.out.println(bestRange(arr));

       /* Arrays.sort(arr, new Comparator<Meeting>() {
            @Override
            public int compare(Meeting o1, Meeting o2) {
                return o1.end - o2.end;
            }
        });*/
        pt(arr);



    }

    // 贪心算法
    public static int bestRange(Meeting[] arr) {
        if (arr == null) return 0;

        // 按照会议结束时间进行排序,然后根据每个会议开始时间与会议室的结束时间比较
        Arrays.sort(arr, new Comparator<Meeting>() {
            @Override
            public int compare(Meeting o1, Meeting o2) {
                return o1.end-o2.end;
            }
        });

        int ans = 0;
        int meetingend = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].start >= meetingend) {
                meetingend = arr[i].end;
                ans++;
            }
        }
        return ans;
    }

    // for test
    // 暴力递归
    public static int bestRange2(Meeting[] arr) {
        if (arr == null || arr.length ==0) return 0;

        return process2(arr, 0, 0);
    }

    // for test
    /**
     * @Author
     * @param done 举办了多少会议
     * @param meetingEnd 会议室结束时间
     */
    public static int process2(Meeting[] arr, int done, int meetingEnd) {
        if (arr.length == 0) return done;

        int max = done;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].start >= meetingEnd) {
                Meeting[] nexts = removeIndex(arr, i);
                max = Math.max(max, process2(nexts, done+1, arr[i].end));
            }
        }
        return max;
    }
    // for test
    public static Meeting[] removeIndex(Meeting[] arr, int index) {
        Meeting[] newArr = new Meeting[arr.length -1];
        int newIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i != index) {
                newArr[newIndex++] = arr[i];
            }
        }
        return newArr;
    }

    public static int bestRange3(Meeting[] arr) {
        if (arr == null || arr.length ==0) return 0;

        return process3(arr, 0, 0);
    }

    // for test
    /**
     * @Author
     * @param done 举办了多少会议
     * @param meetingEnd 会议室结束时间
     */
    public static int process3(Meeting[] arr, int done, int meetingEnd) {
        if (arr.length == 0) return done;

        int max = done;

        for (int i = 0; i < arr.length; i++) {
            Meeting firstM = arr[i];

            if (firstM.start >= meetingEnd) {
                Meeting[] nexts = removeIndex(arr, i);
                max = Math.max(max, process3(nexts, done + 1, firstM.end));
            }
        }
        return max;
    }

    // 随机生成会议对象
    public static Meeting[] randomGenerate(int maxSize, int maxValue) {
        Meeting[] meetings = new Meeting[(int) (Math.random() * maxSize) + 2];
        for (int i = 0; i < meetings.length; i++) {
            int r1 = (int) (Math.random()*maxValue);
            int r2 = (int) (Math.random()*maxValue);
            if (r1 == r2) {
                meetings[i] = new Meeting(r1, r2+1);
            }else {
                meetings[i] = new Meeting(Math.min(r1, r2), Math.max(r1,r2));
            }
        }
        return meetings;
    }
}
